Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

  1. 1 - 0 - 0 - 0 - 1
  2. |   |   |   |   |
  3. 0 - 0 - 0 - 0 - 0
  4. |   |   |   |   |
  5. 0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Hint:

Try to solve it in one dimension first. How can this solution apply to the two dimension case?

Solution:

  1. import java.util.Random;
  3. public class Solution {
  4.   public int minTotalDistance(int[][] grid) {
  5.     List<Integer> x = new ArrayList<>();
  6.     List<Integer> y = new ArrayList<>();
  8.     for (int i = 0; i < grid.length; i++) {
  9.       for (int j = 0; j < grid[0].length; j++) {
  10.         if (grid[i][j] == 1) {
  11.           x.add(i); y.add(j);
  12.         }
  13.       }
  14.     }
  16.     // get median of x[] and y[] using quick select
  17.     int mx = x.get(quickSelect(x, 0, x.size() - 1, x.size() / 2 + 1));
  18.     int my = y.get(quickSelect(y, 0, y.size() - 1, y.size() / 2 + 1));
  20.     // calculate the total Manhattan distance
  21.     int total = 0;
  22.     for (int i = 0; i < x.size(); i++) {
  23.       total += Math.abs(x.get(i) - mx) + Math.abs(y.get(i) - my);
  24.     }
  25.     return total;
  26.   }
  28.   // return the index of the kth smallest number
  29.   // avg. O(n) time complexity
  30.   int quickSelect(List<Integer> a, int lo, int hi, int k) {
  31.     // use quick sort's idea
  32.     // randomly pick a pivot and put it to a[hi]
  33.     // we need to do this, otherwise quick sort is slow!
  34.     Random rand = new Random();
  35.     int p = lo + rand.nextInt(hi - lo + 1);
  36.     Collections.swap(a, p, hi);
  38.     // put nums that are <= pivot to the left
  39.     // put nums that are  > pivot to the right
  40.     int i = lo, j = hi, pivot = a.get(hi);
  41.     while (i < j) {
  42.       if (a.get(i++) > pivot) Collections.swap(a, --i, --j);
  43.     }
  44.     Collections.swap(a, i, hi);
  46.     // count the nums that are <= pivot from lo
  47.     int m = i - lo + 1;
  49.     // pivot is the one!
  50.     if (m == k)     return i;
  51.     // pivot is too big, so it must be on the left
  52.     else if (m > k) return quickSelect(a, lo, i - 1, k);
  53.     // pivot is too small, so it must be on the right
  54.     else            return quickSelect(a, i + 1, hi, k - m);
  55.   }
  56. }